In wireless transmission using a standard-based technology such as WiMAX, Automatic Repeat-reQuest (ARQ) is an error control method that utilizes acknowledgements and timeouts to achieve reliable data transmission and reception. Each connection is identified by a connection identification (CID) and allows the transmission of multiple service data units (SDUs). Each SDU may be fragmented or divided into one or more data blocks (“BLKs”), where each BLK is identified by a Block Sequence Number (BSN). During transmission, one or more data blocks are grouped into fragments (“FRs”) that are first transmitted in sequence in the order of their BSN to the receiver to be reassembled. Each fragment can have one or more sequentially ordered data blocks that are identified by their BSN.
An index may be used to identify a particular CID, SDU, FR, or BLK herein. Thus, for example, a CIDi may represent the ith connection, an SDUi may represent the ith service data unit, an FRi may represent the ith fragment, and a BLKi may represent the ith data block.
An FR can be transmitted more than once if the transmitter does not receive an acknowledgement before the retry timer for the block times out. The first time a fragment is transmitted is referred to herein as the first transmission for the fragment.
FIG. 1 is a representation of an example of an organization of the data for transmission and the transmission sequence for the fragments as defined by IEEE 802.16 for WiMAX. The data to be transmitted has “i” connections represented by the CID list, CID1 through CIDi. The first connection with CID1 has “k” SDUs represented by an SDU list, SDU1 through SDUk. An SDU1 is fragmented into “m” fragments represented by FR1 through FRm while SDU2 is fragmented into “n” fragments represented by FR1 through FRn.
Each FR within an SDU is first transmitted sequentially. The FR in different SDUs is also first transmitted in the arriving order of the SDU. The dotted arrows in FIG. 1 illustrate the order that FRs are first transmitted. All FRs in SDU1 are first transmitted sequentially, and then the data blocks in SDU2 are first transmitted sequentially. This pattern continues for all the SDUs in a connection.
An acknowledgment is a message sent by the receiver to the transmitter to indicate that it has correctly received an FR or some FRs.
Typically, each FR to be transmitted has two timers, a life timer that starts when the FR is first transmitted and a retry timer that starts every time the FR is transmitted. The life timeout value for the life timer is greater than the retry timeout value for the retry timer. The retry timer controls the retransmission of an FR if the transmitter has not received the acknowledgement of that FR before the timeout of the retry timer. After an FR is transmitted, the transmitter waits for an acknowledgement of receipt of the FR from the receiver. If an acknowledgment is not received by the transmitter when the retry timer times out, the retry timer is restarted and the transmitter re-transmits the FR. This process is repeated until the life timer for the FR times out. When a life-timer of an FR times out, the transmitter sends a discard message to the receiver for that particular FR. On receiving the discard message, the receiver may discard the FR and all preceding FRs, i.e., FRs preceding in transmission sequence to the particular FR, and send an acknowledgement message for the FR and all the proceeding FRs. After receiving the acknowledgement, the transmitter may then delete that FR and the entire previous FRs. Since FRs in an SDU are first transmitted in time order, i.e., sequentially, and by the arriving order of the SDUs, and all FRs have the same total lifetime value, the life timer for the FRs will time out at the same order that they are first transmitted. See IEEE Std 802.16-2004, IEEE Standard for Local and Metropolitan Area Networks—Part 16: Interface for Fixed Broadband Wireless Access Systems, October 2004, and IEEE P802.16e-2005, Draft IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems, Amendment for Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands, and Corrigendum 1, February 2006.
The number of timers in a system is a provisioned number in an operating system. Each timer has a timer identification and a corresponding timer data structure. To open or close a timer, the operating system must undergo an inserting or deleting procedure from a timer link list that is operating system specific. Therefore, a system that requires the use of a large number of timers is expensive, both in terms of data memory and the operation of the timers.
Current methods for managing data blocks of fragments require the use of two timers for each data block or fragments. As defined by IEEE 802.16, the maximum number of fragments in the transmission window for a CID connection is 1024. Therefore, the maximum number of timers needed for transmission is 2*1024 for each CID connection. The number of timers required for even few CID connections is therefore very large. Using existing methods, the operating system has to be prepared to reserve a significant amount of its resource for the timers and their operations.
During reception, a fragment FRi, can be characterized by the following: the index “i”, its arrival sequence number that is an indication of its sequence of arrival; the start BSNi or BSNi of FRi, the lowest BSN of the BLKs of Fri; and, ti, the time of its arrival. Therefore, FR1 is the first fragment to arrive while FR2 is the second fragment to arrive. For the two fragments FRi and FRj, if j>i, then tj>ti. Although fragments are transmitted sequentially in the order of their start BSN, they do not necessarily arrive in order due to loss and retransmission. Thus, BSNi may or may not be lower than BSNj.
A receiver window for each connection is managed with a receiver bitmap, where each bit of the bitmap represents a BSN block and the bitmap is ordered in the BSN sequence. Each bit is used to keep tracking whether its corresponding block has been received by the receiver or not. The window is defined by two pointers: one is a lower bound pointer and also referred to as the window-start BSN, and the other pointer is an upper bound pointer and also referred to as the window-highest BSN. The window-start BSN is the lower bound of the BSN of the receiver window and points to the lowest BSN of the BLK that has not been received yet. All blocks with BSN less than the window-start BSN are considered to have been correctly received. All currently received blocks have BSNs that are lower than the window-highest BSN, where the window-highest BSN block indicates an unreceived block with a BSN that is 1 higher than the highest BSN of the currently received blocks.
FIG. 2 is an illustration of a receiver window with four received fragments, FR1 through FR4 that have arrived in that sequence. The receiver window bitmap indicates whether a block in the receiver window has been received or not, where “0” indicates that the data block with that BSN has not been received, while “1” indicates that the block with that BSN has been received. Different fragments can contain a different number of data blocks. For example, FR1 contains 2 data blocks while FR3 only has 1 data block. In FIG. 2, the window-start-BSN is “x”. BLKs may arrive at the receiver out of order relative to their BSN as the result of packet loss and retransmissions. In FIG. 2, FR1 that arrived first contains blocks with BSNs higher than the data blocks in FR2 which has a later arrival time.
At the beginning of the reception process, before the receipt of any data, the window-start-BSN and the window-highest BSN both are at the lowest BSN as there are no received blocks in the window. As fragments containing blocks are received, window-start BSN and window-highest BSN may increase and start moving forward. Using the example in FIG. 2, after FR1 has been received, the window-start BSN remains the same but the window-highest BSN is moved to x+7. These two pointers remain the same as FR2 is received. However, the receipt of FR3 moves the window-highest BSN pointer to x+8.
Current methods using the IEEE 802.16 standard uses purge timers to manage the moving forward of the receiver window if window-start BSN has not moved to a previously received block for some time period. As illustrated in FIG. 2, a purge timer, as indicated by “pi” where i is the index for the time, is started for each received fragment with a start BSN that is not equal to the window-start BSN. This purge timer for this received fragment is closed when the window-start-BSN is moved forward past the start BSN for this fragment. A timer assigned to and started for FRi, is identified as “pi”. The timeout value for a purge timer is PL, the purge life for a fragment. Using the current methods, as indicated in FIG. 2, each fragment in the receiver window can be characterized by their arrival sequence number, start BSN, purge timer, and arrival time.
The window-start BSN is moved forward when one of two conditions is met. The first condition is the arrival of a received block in a received fragment with a BSN that matches the window-start BSN. The second condition is the timeout of a purge timer assigned to a received fragment in the receiver window. When the BSN of a received block in a received fragment matches that of the window-start BSN, the window-start BSN will move forward to the BSN of the first unreceived block. When a purge timer assigned to a received fragment times out, the window-start BSN will move forward to the first un-received block after that fragment. When the window-start-BSN moves forward, it will close the purge timers opened or started and assigned to any fragments along its path forward to the location of the new window-start-BSN.
There may be circumstances when one or more data blocks or data fragments are not received after a pre-determined number of re-transmissions. In order to avoid the situation where the receiver window is stuck at these data blocks, the receiver window will purge these unreceived blocks and continue with normal operation. That is, when a purge timer assigned to a fragment times out, the receiver will force the lower bound of the receiver window to move forward past the fragment with the timed out purge timer and to the first unreceived data block as if all fragments and data blocks, including the fragment with the timed out purge timer, have been received.
Current methodology uses a purge timer for each fragment in the receiver window. See IEEE Std 802.16-2004, IEEE Standard for Local and Metropolitan Area Networks—Part 16: Interface for Fixed Broadband Wireless Access Systems, October 2004; and IEEE P802.16e-2005, Draft IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems, Amendment for Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands, and Corrigendum 1, February 2006.
The maximum window size of a connection, identified by a connection identification (“CID”) can reach 1024 as defined in IEEE Standard 802.16. Therefore, the maximum number of purge timers needed for the receiver is 1023 for each CID connection. This occurs when each fragment in the connection has only one data block. If a few CID connections are configured, the number of purge timer required can be very large.
The number of timers in a system is a provisioned number in the operating system. Each timer has a timer identification and a timer data structure. For run time operations to open or close a timer and for timeout procedures, the operating system has to go through an inserting and deleting procedure from a timer link list that is operating system specific. If there are a large number of purge timers, the operating system has to preserve a significant amount of its resources for the management of these purge timers, their identification, data structure, and their operations. Therefore, a receiver that uses a lot of timers is expensive, both for the data memory and the operation of the timers.
Due to the limitations of the prior art, it is therefore desirable to have novel approaches or methods for the management of transmission and/or receiving of fragments that would minimize the number of timers needed.